package impl.sort;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 05/10/2011
 * Time: 13:28:32
 * To change this template use File | Settings | File Templates.
 */
public class QuickMedianOfThreeSorter extends AbstractSorter {
    public QuickMedianOfThreeSorter() {
        super(SorterType.QUICK_MED_OF_THREE);
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        sort(c, list, 0, list.size()-1);
    }
    private <T> void sort(Comparator<T> c, List<T> list, int l, int r) {
        if(l<r){
            int pivot = r;
            if(r-l>=3){
                int a = r-2;
                int b = r-1;
                if((greater(c, list, a, b) && greater(c, list, r, a)||
                        (greater(c, list, b, a) && greater(c, list, a, r)))){
                    pivot = a;
                }else if((greater(c, list, b, a) && greater(c, list, r, b)||
                        (greater(c, list, a, b) && greater(c, list, b, r)))||
                        equals(c, list, a, b)){
                    pivot = b;
                }
            }
            int i = l;
            int j = r;
            if(pivot==r){
                j = r-1;
            }
            while(i!=j){
                while((!greater(c, list, i, pivot))&&(i<j)){
                    i++;
                    if(i==pivot){
                        i++;
                    }
                }
                while((greater(c, list, j, pivot))&&(j>i)){
                    j--;
                    if(j==pivot){
                        j--;
                    }
                }
                if(i!=j){
                    swap(list, i, j);
                }
            }
            if(i==pivot+2){
                i--;
            }
            if((greater(c, list, i, pivot) && i<pivot)||(greater(c, list, pivot, i) && pivot<i)){
                swap(list, pivot, i);
                pivot = i;
            }
            sort(c, list, l, pivot-1);
            sort(c, list, pivot+1, r);
        }
    }
}